class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        vector<int> ret;
        int left = 0,right = price.size()-1;
        while(left < right)
        {
            if(price[left] + price[right] > target)
            {
                --right;
            }
            else if(price[left] + price[right] < target)
            {
                ++left;
            }
            else
            {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};
class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> ret;
        int n = nums.size();
        // 排序
        sort(nums.begin(),nums.end());
        // 去重要注意到的两个地方 ： left和right要去重，i也要去重 
        for(int i = 0;i<n;)  // [这里不能i++，循环最下面已经将i更新为下一个数的下标了]
        {
            if(nums[i] > 0 )// 保证i下标的数是小于等于0的，因为第一个数都大于0了，后面的数也是大于0的
            {
                break;
            }
            int left = i+1,right = n-1;
            while(left < right)
            {
                if(nums[left] + nums[right] + nums[i] > 0)
                {
                    --right;
                }
                else if(nums[left] + nums[right] + nums[i] < 0)
                {
                    ++left;
                }
                else
                {
                    ret.push_back({nums[left],nums[right],nums[i]});

                    // 不能遗漏，继续进行操作，查找剩下的三元组
                    ++left;
                    --right;

                    // 去重
                    while(nums[left] == nums[left-1] && left < right)
                        ++left;
                    while(nums[right] == nums[right+1] && left < right)
                        --right;
                }
            }
            // 去重
            ++i;
            while(i<n && nums[i] == nums[i-1])
                ++i;
        }
        return ret;
    }
};
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        int n = nums.size();
        // 排序
        sort(nums.begin(),nums.end());
        // 去重要注意到的两个地方 ： left和right要去重，j要去重，i也要去重 
        for(int i = 0;i<n;)
        {
            for(int j=i+1;j<n;)
            {
                int left = j+1,right = n-1;
                while(left < right)
                {
                    // 【target是负的最大数的时候，在减去两个值就越界了，强转成为long long类型就不会了】
                    long long aim = (long long)target - nums[i] -nums[j]; 
                    if(nums[left] + nums[right] > aim)
                    {
                       --right;
                    }
                    else if(nums[left] + nums[right] < aim)
                    {
                        ++left;
                    }
                    else
                    {
                        ret.push_back({nums[left],nums[right],nums[i],nums[j]});

                        // 不能遗漏，继续进行操作，查找剩下的四元组
                        ++left;
                        --right;

                        // 去重
                        while(nums[left] == nums[left-1] && left < right)
                            ++left;
                        while(nums[right] == nums[right+1] && left < right)
                            --right;
                    }
                }
                // 去重
                ++j;
                while(j<n && nums[j] == nums[j-1])
                    ++j;
            }
            // 去重
            ++i;
            while(i<n && nums[i] == nums[i-1])
                ++i;
        }
        return ret;
    }
};
